public class Solution1254 {

    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};

    public int closedIsland(int[][] grid) {
        boolean[][] visit=new boolean[grid.length][grid[0].length];
        for (int i=0;i<grid[0].length;i++){
            if (!visit[0][i] && grid[0][i]==0){
                dfs(grid,visit,0,i);
            }
        }
        for (int i=0;i<grid[0].length;i++){
            if (!visit[grid.length-1][i] && grid[grid.length-1][i]==0){
                dfs(grid,visit,grid.length-1,i);
            }
        }
        for (int i=0;i<grid.length;i++){
            if (!visit[i][0] && grid[i][0]==0){
                dfs(grid,visit,i,0);
            }
        }
        for (int i=0;i<grid.length;i++){
            if (!visit[i][grid[0].length-1] && grid[i][grid[0].length-1]==0){
                dfs(grid,visit,i,grid[0].length-1);
            }
        }
        int ans=0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (!visit[i][j] && grid[i][j]==0){
                    ans++;
                    dfs(grid,visit,i,j);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] grid, boolean[][] visit, int x, int y) {
        visit[x][y]=true;
        for (int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (xx>=0 && xx<grid.length && yy>=0 && yy<grid[0].length && !visit[xx][yy] && grid[xx][yy]==0){
                dfs(grid,visit,xx,yy);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1254().closedIsland(new int[][]{{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0,1},{1,1,1,1,1,1,1,0}}));
    }
}
